package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: 647. 回文子串
 * @author: STU756
 * @create: 2020-08-19 02:13
 */
public class Pro0647 {
    //动态递推   O(N^2)  10^6符合   可以压缩空间为O(n)
    public int countSubstrings(String s) {
        int len;
        if(s == null || (len = s.length()) == 0) return 0;
        boolean[][] dp = new boolean[len][len];
        int ans = 0;
        //dp[i][j] =
        for(int i = 0; i < len; i++) {
            for(int j = i; j>=0; j--) {
                if(i == j) dp[j][i] = true;
                else if(i - j == 1 && s.charAt(i) == s.charAt(j)) {
                    dp[j][i] = true;
                }else if(i - j > 1) {
                    dp[j][i] = dp[j+1][i-1] && s.charAt(i) == s.charAt(j);
                }
                if(dp[j][i]) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    //暴力超时
    public int countSubstrings2(String s) {
        int len;
        if(s == null || (len = s.length()) == 0) return 0;
        int ans = 0;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                int L = j, R = i;
                boolean flag = true;
                while(L <= R) {
                    if(s.charAt(L) != s.charAt(R)) {
                        flag = false;
                        break;
                    }
                }
                if(flag) ++ans;
            }
        }
        return ans;
    }
}
